package com.lun.swordtowardoffer2.c08;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class ContainsNearbyAlmostDuplicate {

	//方法一：时间复杂度为O(n log k)的解法
	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
		TreeSet<Integer> set = new TreeSet<>(); 
		for(int i = 0; i < nums.length; i++) {
			
			int cur = nums[i];
			Integer lower = set.floor(cur);
			if(lower != null && cur - lower <= t) {
				return true;
			}
			
			Integer upper = set.ceiling(cur);
			if(upper != null && upper - cur <= t) {
				return true;
			}
			
			set.add(cur);
			if(i >= k) {//超过范围的及时去除
				set.remove(nums[i - k]);
			}
		}
		
		return false;
	}
	
	//方法二：时间复杂度为O(n)的解法
	public boolean containsNearbyAlmostDuplicate2(int[] nums, int k, int t) {
		Map<Integer, Integer> buckets = new HashMap<>();
		int bucketCapicity = t + 1;//
		
		for(int i = 0; i < nums.length; i++) {
			int num = nums[i];
			int id = getBucketID(num, bucketCapicity);
			
			if(buckets.containsKey(id)
					|| buckets.containsKey(id - 1) && num - buckets.get(id - 1) <= t
					|| buckets.containsKey(id + 1) && buckets.get(id + 1) - num <= t) {
				return true;
			}
			
			buckets.put(id, num);
			if(i >= k) {
				buckets.remove(getBucketID(nums[i - k], bucketCapicity));
			}
		}
		
		return false;
	}
	
	private int getBucketID(int num, int bucketCapicity) {
		
		return num >= 0 ? num / bucketCapicity : (num + 1) / bucketCapicity - 1;
	}
}
